1. Field of the Invention
The present invention generally relates to a method that allow a set of servers to maintain a set of keys, shared with a client, in the presence of mobile eavesdroppers that occasionally break into servers and learn the entire contents of their memories, and more particularly to efficient schemes for maintaining secret keys common to the user and each of several servers based on periodic key updates. Another application of the invention is to securely generate random numbers in the presence of mobile faults.
2. Description of the Prior Art
The need for ensuring secure communication over insecure channels is becoming increasingly acute. For instance, users ("clients") in a multiuser system may frequently wish to, say, authenticate the identity of their party for conversation, to authenticate a specific message, or even to exchange encrypted messages. Efficient implementations of such primitives for secure communication require the involved parties to first generate a common, secret session key.
A standard solution to the session keys generation problem uses a secure trusted entity, or a server. The system is initialized so that each user has a secret key that is known only to itself and the server. Now, in order to generate a session key, the involved parties engage in a protocol with the server.
A major drawback of the server method is that it hinges on the absolute security of the sever. Namely, if this server is broken into (i.e., the contents of the server's memory becomes known to an adversary), then all the private keys are revealed and the security of the entire system collapses.
Consequently, a scheme is required, in which the security of the system is not compromised even when individual components are broken into. We note that there exists an alternative way for generating secure session keys; namely, use public key cryptographic primitives (e.g., the Revist, Shamir, Adelman (RSA) algorithm). This solution eliminates the need for interacting with a server for generating each session key. However, a secure server is still needed in order to authenticate the public keys. Furthermore, public key cryptography is computationally intensive and relies on stronger computational assumptions.
A straightforward way to enhance the security of the server mechanism may be to "duplicate" the server. Namely, use several servers and have every user execute the interaction protocol with each server. This solution has two major drawbacks. First, it is highly inefficient, since the party must interact with several servers in order to obtain each session key. Second, once every server has been broken into at some time, the system is no longer secure.